1. Technical Field
The present disclosure relates generally to information processing systems and, more specifically, to a low-collision Bloom filter.
2. Background Art
A Bloom filter is a probabilistic algorithm to quickly test membership in a large set using multiple hash functions into an array of bits. The use of Bloom filters is known in the art, and originates from the seminal paper written by B. Bloom, “Space/Time Trade-Offs in Hash Coding with Allowable Errors,” Comm. ACM, vol. 13, no. 7, May 1970, pp. 422-426.
Bloom filters are space-efficient structures that support fast constant-time insertion and queries. A Bloom filter supports (probabilistic) membership queries in a set A={a1, a2, . . . , an} of n elements (also called keys).
A Bloom filter quickly filters (i.e., identifies), non-members without querying the large set by exploiting the fact that a small percentage of erroneous classifications can be tolerated. When a Bloom filter identifies a non-member, it is guaranteed to not belong to the large set. When a Bloom filter identifies a member, however, it is not guaranteed to belong to the large set. In other words, the result of the membership test is either: it is definitely not a member, or, it is probably a member.